МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Структура даних ЧЕРГА МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 4 з дисципліни " Програмування. Частина III. Структури даних та алгоритми " для студентів напряму 6.050102 “Комп’ютерна інженерія” Львів – 2012 Методичні вказівки до лабораторної роботи "Структура даних ЧЕРГА" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А. Матвейчук – Львів: Видавництво НУ “Львівська політехніка”, 2012 – 12 с. Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ Відповідальний за випуск: Мельник А.О., д-р техн. наук, проф. Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ Юрчак І.Ю., доцент кафедри САПР, к.т.н.  1. МЕТА РОБОТИ Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. 2. ТЕОРЕТИЧНІ ВІДОМОСТІ Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO. Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу. Приклад : В послідовності 8 2 6 3 1 4 9 кожна парна цифра визначає операцію push (додавання цієї цифри в чергу), а кожна непарна цифра визначає операцію pop (вилученя з черги одного елемента). Введемо такі позначення: P – покажчик початку черги, К – покажчик кінця черги Наведемо динаміку вмісту черги під час обробки заданої послідовності:  K P  0)       - порожня черга      P K   P K   P K  1) 8       2) 8 2      3) 8 2 6        P K   P K   P K  4)  2 6     5)   6     6)   6 4       P K      7)    4            Оскільки черга - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас queue, для використання якого потрібно включити заголовочний файл: # include <queue> Набір стандартних операцій роботи з чергою показаний у таблиці: Операція Дія  push(іtem) Поміщає новий елемент у кінець черги  pop() Вилучає елемент з черги, але не повертає його значення  front() Повертає значення елемента з початку черги, але не вилучає його  empty() Повертає true, якщо черга порожня, і false у противному випадку  sіze() Повертає кількість елементів у черзі   Розглянемо статичну реалізацію черги на основі масиву з фіксованим рзміром. В наведенному далі лістінгу показано заголовочний файл для шаблонного класу queue, аналогічний класу queue зі стандартної бібліотеки шаблонів STL. // ФАЙЛ: queue1.h (частина простору імен main_savitch_8B) #ifndef MAIN_SAVITCH_QUEUE1_H #define MAIN_SAVITCH_QUEUE1_H #include <cstdlib> // Provides size_t namespace main_savitch_8B { template <class Item> class queue { public: // ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ typedef std::size_t size_type; typedef Item value_type; static const size_type CAPACITY = 30; // КОНСТРУКТОР queue( ); // МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ void pop( ); void push(const Item& entry); // КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ bool empty( ) const { return (count == 0); } Item front( ) const; size_type size( ) const { return count; } private: Item data[CAPACITY]; size_type first; size...